The Moving Picture Experts Group (MPEG) MPEG-2 Standard is a compression/decompression standard for video applications. The standard describes an encoded and compressed data stream that has substantial bandwidth reduction. The compression is a subjective lossly compression. The encoded, compressed digital video data is subsequently decompressed and decoded in an MPEG-2 Standard compliant decoder.
The MPEG-2 Standard is described in, e.g., C. A. Gonzales and E. Viscito, "Motion Video Adaptive Quantization In The Transform Domain," IEEE Trans Circuits Syst Video Technol, Volume 1, No. 4, December 1991, pp. 374-378, E. Viscito and C. A. Gonzales, "Encoding of Motion Video Sequences for the MPEG Environment Using Arithmetic Coding," SPIE, Vol. 1360, pp. 1572-1576, (1990), D. LeGall, "MPEG: A Video Compression Standard for Multimedia Applications," Communications of the ACM, Vol. 34, No. 4, (April 1991), pp. 46-58, S. Purcell and D. Galbi, "C Cube MPEG Video Processor," SPIE, v. 1659, (1992) pp. 24-29, and D. J. LeGall, "MPEG Video Compression Algorithm," Signal Process Image Commun, v.4, n. 2, (1992), pp. 129-140, among others.
The MPEG-2 Standard specifies a data stream format and a decoder for a very high compression technique that achieves overall image data stream compression not achievable with either intraframe coding alone or interframe coding alone, while preserving the random access advantages of pure intraframe coding. The combination of block based frequency domain intraframe encoding and interpolative/predictive interframe encoding of the MPEG-2 Standard results in a balance between intraframe encoding alone and interframe encoding alone.
The MPEG-2 Standard exploits temporal redundancy for motion compensated interpolative and predictive encoding. That is, the assumption is made that "locally" the current picture can be modeled as a translation of the picture at a previous and/or future time. "Locally" means that the amplitude and direction of the displacement are not the same everywhere in the picture.
The MPEG-2 Standard specifies predictive and interpolative interframe encoding and frequency domain intraframe encoding. It has block based motion compensation for the reduction of temporal redundancy, and block based Discrete Cosine Transform based compression for the reduction of spatial redundancy. Under the MPEG-2 Standard, motion compensation is achieved by predictive coding, interpolative coding, and Variable Length Coded motion vectors. The information relative to motion is based on a 16.times.16 array of pixels and is transmitted with the spatial information. Motion information is compressed with Variable Length Codes, such as Huffman codes.
The motion compensation unit under the MPEG-2 Standard is the Macroblock unit. The MPEG-2 Standard Macroblocks are 16.times.16 pixels. Motion information consists of vectors for forward predicted macroblocks, vectors for backward predicted macroblocks, and vectors for bidirectionally predicted macroblocks. The motion information associated with each macroblock is coded differentially with respect to the motion information present in the previous macroblock. In this way a macroblock of pixels is predicted by a translation of a macroblock of pixels from a past or future picture.
The difference between the source pixels and the predicted pixels is included in the corresponding bit stream. The decoder adds a correction term to the block of predicted pixels to produce the reconstructed block.
In a typical block matching search for video encoding motion estimation, the reference search area is rectangular in shape. The width and height of this rectangle is referred to as the search range, as it represents a portion of the reference frame around the position of the macroblock to be coded in which a best match result is sought to compensate for motion between the current and reference frames. The larger the search range, the better the chance to find a nearly identical macroblock to the one being encoded. With a good match, fewer bits are needed to encode the macroblock since all that is required is the vector showing the displacement from the current macroblock, and the small differences between the macroblocks.
High definition video requires large search ranges due to its higher resolutions. The full size of a high definition television (HDTV) frame makes encoding the entire picture by a single encoder prohibitive. Conventionally, multiple encoders are employed, with each encoder encoding a portion of the picture. The portions are then stitched together to create one encoded stream. Motion searching needs to overlap at the seams (i.e., the borders of each encoder's portion of the whole picture), to minimize visual artifacts.
Increasing the search range by simply increasing the maximum size of the rectangle is one possible solution, but may have an adverse effect on encoder performance. Generally, the larger the search range, the more time it takes to perform the search. Increasing the maximum rectangle also entails adding more data storage capability on chip, which will increase encoder size and power consumption.
In view of the above, and in order to establish commercial advantage, a novel approach is needed for performing macroblock match searching during video encoding motion estimation, particularly for high definition video.